# leetcode 101 对称二叉树

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def compare(left, right):
            if left is None and right is not None:  # 左节点为空，右节点不为空
                return False
            elif left is not None and right is None: # 左节点不为空，右节点为空
                return False
            elif left and right and (left.val != right.val): # 左右节点值不相等
                return False
            elif left is None and right is None: # 左右节点为空
                return True
            elif left and right and (left.val == right.val): # 左右节点能够相互翻转
                ret_left = compare(left.left, right.right)   # 然后将左子树的左节点和右子树的右节点进行相互比较，即外侧比较
                ret_right = compare(left.right, right.left)  # 再将左子树的右节点和右子树的左节点进行比较，即内侧比较
                return ret_left and ret_right                # 当两侧都为true，返回true
        return compare(root.left, root.right)
